Error correcting codes are digital codes that can generally be used to detect and/or correct errors in transmitted information bits. For example, error correcting codes can include redundant bits, e.g., check bits or parity bits, that can indicate errors in transmitted information and correct information bit errors. Data storage and digital communication systems typically use error correcting codes to operate reliably.
One category of error correcting codes includes block error correcting codes. Block error correcting codes can take a given number of information bits, k, and generate an n-bit long codeword or codevector by including n-k parity bits. The length of a codevector and number of information bits the codevector uses can be denoted [n, k].
Cyclic codes are types of block error correcting codes in which a cyclic shift of a codevector can produce another codevector. For example, if an n-bit codevector from a cyclic code is regarded as being wrapped into a circle, then any right or left shift of the codevector can produce another codevector.
Cyclic codes can be encoded with bit-serial encoders that use single bit registers and single bit combinational logic. The single bit registers can be arranged in a string to make a shift register. Data can propagate from single bit register to single bit register along the shift register. For each clock cycle, the most significant single bit register can output one bit.
A cyclic code encoder's incoming information bits can be combined with a register output to generate a feedback signal that is injected at the input of each single bit register. The bit-serial cyclic encoder's combinational logic can 1) multiply the feedback signal by binary weights equal to generator polynomial coefficients, then 2) supply the weighted feedback signals to the single bit registers. The combinational logic can weight or multiply the feedback signal by a different generator coefficient at the input to each single bit register. A binary generator coefficient is a multiplier that connects or disconnects the feedback signal to a register input to multiply the feedback signal by one or zero, respectively.
FIG. 1 shows a conventional bit-serial [n, k] binary cyclic encoder 100 that transfers k information bits 101 to the encoder output in the following order: Uk-1, Uk-2, . . . , U0, where the Uk-1 bit is the most significant bit of information bits 101. Information bits 101 can be described equally well in either the polynomial form U(x)=U0+U1x+ . . . +Uk-2xk-2+Uk-1xk-1 or in vector form as a k-element long vector U=[U0, U1, . . . , Uk-2, Uk-1]. In the vector form, the most significant information bit can be shown on the right; this convention conveniently matches the order in which information bits emerge from a bit-serial cyclic encoder.
After encoder 100 accepts the k information bits, encoder 100 can generate N=n−k parity bits 107, and then output the parity bits after the information bits. The parity bits can be arranged as a parity bit vector P=[P0, P1, . . . , PN-2, PN-1] that is appended to the information bit vector to form a codevector 102. Codevector 102 can be represented as an n-element long vector, V, in the form:V=[V0, V1, . . . , Vn-2, Vn-1]=[P0, P1, . . . , PN-2, PN-1, U0, U1, . . . , Uk-2, Uk-1]  EQ. 1
As shown, the information bits, U, in EQ. 1 appear explicitly as the most significant bits of codevector 102. An error correcting code in which the information bits appear explicitly is called a systematic code. All cyclic codes can be made systematic. Encoder 100 of FIG. 1 is systematic because encoder 100 accepts and places information bits 101 so that information bits 101 appear explicitly in adjacent, sequential positions in codevector 102. A clock signal (not shown) synchronizes the flow of information bits 101.
A multiplexer 104 routes information bits 101 to codevector 102 when an information/parity selection 103 is asserted. Multiplexer 104 routes parity bits 107 from a register 110 when information/parity selection 103 is de-asserted. Information bits 101 appear serially in codevector 102, with the most significant information bit, Uk-1, first followed by sequentially generated (bit-serial) parity bits, starting with PN-1.
Each bit of information bits 101 is added to a parity bit 107 to generate a feedback signal 109. The initial value of parity bit 107 is zero because each register 110, 120, . . . 170 is initialized to zero before the arrival of information bits 101. An opening gate 106 generates a zero feedback signal that initializes each register 110, 120, . . . , 170 to zero before a new codevector 102 is generated.
Encoder 100 uses a digital feedback loop to generate the parity bits. The feedback loop is closed only while the information bits stream out of the encoder. Afterward, the feedback loop opens and the parity bits emerge serially from the output of the shift register and are routed to the codevector 102 through multiplexer 104.
An adder 108 generates feedback signal 109 by combining each bit of information bits 101 and parity bit 107 by using modulo-2 arithmetic (i.e., each addition of two binary numbers produces a sum that is either a zero or a one). Adder 108, as well as adders 112, 122, 132, 142, 152, and 162, can each be implemented using an exclusive-OR gate (XOR). The output of an exclusive OR is “1” when the inputs of the gate differ and “0” when the inputs agree.
An encode command 105 closes gate 106 while information bits 101 are being routed to codevector 102. Gate 106 provides (active) feedback signal 109 to generator coefficients or weight components 111, 121, 131, 141, 151, 161, and 171 as long as gate 106 is closed and zero otherwise. Gate 106 remains closed during the time information bits 101 are being routed to codevector 102.
After information bits 101 have been routed to codevector 102, encode command 105 opens gate 106 to open the feedback loop. Thereafter registers 170, 160, 150, etc. each shift their contents towards register 110. Simultaneously, register 110 sends parity bits 107 to multiplexer 104.
Registers 170, 160, 150, etc. are each loaded with a zero sequentially after the feedback loop opens. The zeroing process starts with the least significant register, e.g. register 170, which outputs a zero on the first clock pulse after gate 106 opens. Each register (170, 160, 150, etc.) fills with zero on successive clock pulses until all registers contain zero and all parity bits have been routed to codevector 102 by multiplexer 104.
When gate 106 is closed, feedback signal 109 encounters weight components 111, 121, . . . 171, (i.e., 111-171) en route to each register. Each weight component 111-171 can be thought of as a binary multiplier, i.e., a “0” or “1” multiplier that respectively corresponds to an open or closed connection. Accordingly, particular connections which implement of some weight components 111-171 can be absent while other connections can provide feedback signal 109 to adders 112, 122, . . . 162.
The bit-serial cyclic encoder of FIG. 1 generates the parity bits by 1) weighting the feedback signal by generator or weight coefficients 111-171, 2) combining the weighted feedback with register contents, and 3) shifting the combination into the registers. In operation, while the feedback path is closed, generator or weight coefficients each multiply the cyclic encoder's feedback signal by either a zero (0) or one (1) weight, the weighted feedback signal is added to any previous shift register output, then the sum is provided to the next shift register's input. The generator or weight coefficients 111-171 in FIG. 1 can be called gi, where 0≦i≦N=n−k−1, and are taken as the respective coefficients of the cyclic code generator polynomial:g(X)=g0+g1x+ . . . +gJ-1xJ-1+gJxJ . . . +gN-3xN-3+gN-2xN-2+gN-1xN-1+xN  EQ. 2
The maximum clock speed of bit-serial cyclic encoders can be constrained by shift register data setup time and combinational logic gate delay for circuitry in a critical path of the feedback loop. The critical path is the path containing the longest latency or signal delay.
Conventional bit serial encoders, e.g., encoders that generate and output parity bits one at a time, have a critical path with two binary adders, e.g., two XORs, and one AND gate. For each information bit received, the first XOR adds the previous parity bit to the information bit, thereby forming the feedback signal. The feedback signal propagates through a second intra-register adder (XOR) to supply an input to a register in the shift register. The critical path of a bit-serial cyclic encoder therefore incurs two XOR delays. The critical path time accounts for these two XOR delays, plus the propagation delay for an AND gate that can apply a programmable generator coefficient, plus the setup time for a register. The equation for the critical path delay for a programmable bit serial encoder is therefore:t1 bit=2tXOR+tAND+tSETUP  EQ. 3Since one parity bit is generated per clock cycle, then a clock speed of 1 GHz will generate 1 parity bit per clock period, e.g., 1 nanosecond (ns). However, the propagation delays and setup time of the combinational logic and registers may be a substantial fraction of the clock period and may limit the top speed or maximum clockable rate of a bit-serial cyclic encoder.